package likou;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Info: 378. 有序矩阵中第K小的元素
 * @Author: 唐小尊
 * @Date: 2020/7/2  18:32
 */
public class _378 {
    //存储每一行的当前列
    static List<Integer> colIndex = new ArrayList();
    static int maxRowIndex = 0;

    public static void main(String[] args) {
        colIndex.add(0);
        int[][] matrix = {{1, 5, 9}, {10, 11, 13}, {12, 13, 15}};
//        for (int i=0;i<matrix.length*matrix.length;i++){
//            System.out.println(getMin(matrix));
//        }
        System.out.println(kthSmallest(matrix,3));
    }

    public static int getMin(int[][] matrix) {
        int min = -999;//如果越界就是
        int row = 0, col = 0;
        //从每行中找出最小的一个（每行当前遍历到的位置即为该行最小的一个）
        for (int i = 0; i <= maxRowIndex; i++) {
            if (colIndex.get(i) >= matrix.length) {//如果当前行全部放进去，就下一行
                continue;
            }
            if (min == -999) {//初始化min
                min = matrix[i][colIndex.get(i)];
                row = i;
                col = colIndex.get(i);
                continue;
            }
            if (min > matrix[i][colIndex.get(i)]) {
                min = matrix[i][colIndex.get(i)];
                row = i;
                col = colIndex.get(i);
            }
        }
        //如果是第一列的最后一个且该行不为最后一行，则maxRowIndex就加一
        if (col == 0 && row == maxRowIndex && maxRowIndex < (matrix.length - 1)) {
            maxRowIndex++;
            colIndex.add(0);
            colIndex.set(row, col + 1);
        } else {
            colIndex.set(row, col + 1);
        }
        return min;
    }


    public static int kthSmallest(int[][] matrix, int k) {
        int rows = matrix.length, columns = matrix[0].length;
        int[] sorted = new int[rows * columns];
        int index = 0;
        for (int[] row : matrix) {
            for (int num : row) {
                sorted[index++] = num;
            }
        }
        Arrays.sort(sorted);
        return sorted[k - 1];
    }
}
